/**
 * @(#)LC02两数相加.java, 9月 27, 2021.
 * <p>
 * Copyright 2021 fenbi.com. All rights reserved.
 * FENBI.COM PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package com.wxweven.algorithm.list;

/**
 * @author wxweven
 */
public class LC02两数相加 {

    /*
     * 题目描述：
     *
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     *
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     *
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *
     * 示例：
     *
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     */

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }

        if (l2 == null) {
            return l1;
        }

        // 每次相加的和
        int sum = 0;
        // 相加和的进位
        int add = 0;

        // 这里加一个无用的dummy节点，最终结果返回dummy.next
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (l1 != null || l2 != null) {
            // l1 或 l2 为null，就按0处理来相加，记得加上进位
            sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + add;

            // 进位就是和除以10
            add = sum / 10;

            // 最终要保留的是对10求余
            sum = sum % 10;

            cur.next = new ListNode(sum);
            cur = cur.next;

            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }

        // 考虑最高位相加后，仍有进位的特殊情况
        if (add > 0) {
            cur.next = new ListNode(add);
        }

        return dummy.next;
    }
}